Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт до лабораторної роботи № 3
На тему:
“Алгоритм шифрування з відкритим ключем RSA”
Варіант №4
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
Завдання
На основі інструментарію Visual C++ 2005 розробити Windows Forms програму CLR для реалізації вказаного проекту алгоритму криптографічної системи з відкритими ключами RSA.
Усі окремі алгоритми (наприклад, обчислення НСД бінарним алго ритмом Евкліда) реалізувати у вигляді підпрограм (функцій).
З метою компактності у завданні вказуються лише номери алгоритмів, на основі яких потрібно реалізувати загальний проект програ ми RSA. Розшифрування номерів подаються тут:
1. Алгоритм піднесення до степеню: 1.1. Метод справа-наліво двійкового потенціювання; 1.2. Метод зліва-направо двійкового потенціювання; 1.3. Рекурсивний метод двійкового потенцію вання; 1.4. Метод вікна; 1.5. Метод змінного вікна.
2. Обч. найбільшого спільного дільника: 2.1. Алгоритм Евклі да; 2.2. Бінарний алгоритм Евкліда.
3. Обч. оберненого значення за модулем: 3.1. Розширений ал горитм Евкліда; 3.2. Розширений бінарний алгоритм Евкліда.
4. Тести визначення простоти числа: 4.1. Тест Рабіна-Мілера; 4.2. Тест Соловея-Штрасена; 4.3. Тест Лемана.
Файл #6
Алг: 1.4; 2.1; 3.1;
Теоретичні відомості
Метод вікна.
У більшості випадках, піднесення до квадрату виконується швидше, аніж загальне множення. І відповідно, для того щоби ще більше скоротити час обчислень, варто спробувати зменшити кількість загальних добутків. Це є можливим при використанні техніки вікон, яка використовує наперед обчислені значення.
Ідея методу базується на виборі для показника степеню осно ви системи числення більшої 2. З практичної точки зору основа вибирається рівною степеню двійки: .
У віконному методі за один раз враховується символів вказівника степеню. Спершу обчислюється та запам’ятовується таблиця значень , , … ,
, для
де – ширина вікна.
Далі записуємо число у системі числення за основою
,
де – кількість розрядів у системі числення за основою .
Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок , потім і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
Розширений алгоритм Евкліда.
Звичайний алгоритм Евкліда для знаходження НСД (,) зводився до послідовного ділення із залишком
, , (2.30)
де , , НСД (,).
Якщо для послідовності (2.30) провести ряд перетворень та виразити усі залишки через та , тоді
,
,
,
,
(2.31)
Таким чином, ми отримали рекурентну формулу (2.31) для зна ходження НСД (,) у вигляді лінійної комбінації чисел та з цілими числами та . Якщо числа та взаємно прості, тоді НСД (,) = 1, і відповідно
1 = НСД (,) =. (2.32)
З формули (2.32) випливає, що обернене значення .
Загальний розширений алгоритм Евкліда
обчислення оберненого значення
Мовою С++ цей алгоритм виглядає так:
// обчислення
// вхід: числа a та n, для яких треба знайти nsd= НСД (,)
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
Остаточна версія програми
#pragma once
using namespace System::IO;
namespace Laba3 {
using namespace System;
using namespace System::ComponentModel;
using na...
